#include <iostream>
#include <climits>
using namespace std;
struct int3{
int n1, n2, n3;
int3(int _n1, int _n2, int _n3): n1(_n1), n2(_n2), n3(_n3){}
};
int3 find_max_crossing_subarray(int* arr, int low, int mid, int high){
int left_sum=INT_MIN, right_sum=INT_MIN;
int sum=0, max_left, max_right;
for(int i=mid; i>=low; --i){
sum=sum+arr[i];
if(sum>left_sum){
left_sum=sum;
max_left=i;
}
}
sum=0;
for(int j=mid+1; j<=high; ++j){
sum=sum+arr[j];
if(sum>right_sum){
right_sum=sum;
max_right=j;
}
}
return int3(max_left, max_right, left_sum+right_sum);
}
int3 find_maximum_subarray(int* arr, int low, int high){
if(high==low) return int3(low, high, arr[low]);
else {
int mid=(low+high)/2;
int3 l3=find_maximum_subarray(arr, low, mid);
int3 r3=find_maximum_subarray(arr, mid+1, high);
int3 m3=find_max_crossing_subarray(arr, low, mid, high);
if(l3.n3>=r3.n3 && l3.n3>=m3.n3) return l3;
else if(r3.n3>=l3.n3 && r3.n3>>m3.n3) return r3;
else return m3;
}
}
int main(void){
int tot_arr[]={100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97};
int size=sizeof(tot_arr)/sizeof(int)-1;
int arr[size];
for(int i=0; i<size+1; ++i){
arr[i]=tot_arr[i+1]-tot_arr[i];
}
int3 result=find_maximum_subarray(arr, 0, size-1);
cout<<"from: "<<result.n1<<" to: "<<result.n2<<" sum: "<<result.n3<<endl;
return 0;
}